{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Shortest Superstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #string #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #字符串 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestSuperstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最短超级串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串数组 <code>words</code>，找到以 <code>words</code> 中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件，返回其中 <strong>任意一个</strong> 即可。</p>\n",
    "\n",
    "<p>我们可以假设 <code>words</code> 中没有字符串是 <code>words</code> 中另一个字符串的子字符串。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"alex\",\"loves\",\"leetcode\"]\n",
    "<strong>输出：</strong>\"alexlovesleetcode\"\n",
    "<strong>解释：</strong>\"alex\"，\"loves\"，\"leetcode\" 的所有排列都会被接受。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"catg\",\"ctaagt\",\"gcta\",\"ttca\",\"atgcatc\"]\n",
    "<strong>输出：</strong>\"gctaagttcatgcatc\"</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= words.length <= 12</code></li>\n",
    "\t<li><code>1 <= words[i].length <= 20</code></li>\n",
    "\t<li><code>words[i]</code> 由小写英文字母组成</li>\n",
    "\t<li><code>words</code> 中的所有字符串 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-shortest-superstring](https://leetcode.cn/problems/find-the-shortest-superstring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-shortest-superstring](https://leetcode.cn/problems/find-the-shortest-superstring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"alex\",\"loves\",\"leetcode\"]', '[\"catg\",\"ctaagt\",\"gcta\",\"ttca\",\"atgcatc\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        overlap = [[0] * n for _ in range(n)]\n",
    "        for i, word1 in enumerate(words):\n",
    "            for j, word2 in enumerate(words):\n",
    "                for k in range(min(len(word1), len(word2)), 0, -1):\n",
    "                    if word1[-k:] == word2[:k]:\n",
    "                        overlap[i][j] = k\n",
    "                        break\n",
    "\n",
    "        # 向之后的状态转移\n",
    "        n = len(words)\n",
    "        m = 1 << n\n",
    "        dp = [[0] * m for _ in range(n)]\n",
    "        pa = [[0] * m for _ in range(n)]\n",
    "        for mask in range(1, m):\n",
    "            for i in range(n):\n",
    "                if not mask >> i & 1:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if mask >> j & 1:\n",
    "                        continue\n",
    "                    nxt = mask | (1 << j)\n",
    "                    tmp = dp[i][mask] + overlap[i][j]\n",
    "                    if tmp >= dp[j][nxt]:\n",
    "                        dp[j][nxt] = tmp\n",
    "                        pa[j][nxt] = i\n",
    "                \n",
    "        mask = m - 1\n",
    "        idx = 0\n",
    "        for i in range(n):\n",
    "            if dp[i][mask] > dp[idx][mask]:\n",
    "                idx = i\n",
    "                \n",
    "        ans = words[idx]\n",
    "        while True:\n",
    "            nxt = idx\n",
    "            idx = pa[idx][mask]\n",
    "            mask ^= 1 << nxt\n",
    "            if not mask:\n",
    "                break\n",
    "            ans = words[idx][:len(words[idx])-overlap[idx][nxt]] + ans\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        overlap = [[0] * n for _ in range(n)]\n",
    "        for i, word1 in enumerate(words):\n",
    "            for j, word2 in enumerate(words):\n",
    "                for k in range(min(len(word1), len(word2)), 0, -1):\n",
    "                    if word1[-k:] == word2[:k]:\n",
    "                        overlap[i][j] = k\n",
    "                        break\n",
    "\n",
    "        m = 1 << n\n",
    "        dp = [[0] * m for _ in range(n)]  # 最大重叠长度之和\n",
    "        pa = [[0] * m for _ in range(n)]\n",
    "        for mask in range(1, m):\n",
    "            for i in range(n):\n",
    "                if not mask >> i & 1:\n",
    "                    continue\n",
    "                pmask = mask ^ (1 << i)\n",
    "                for j in range(n):\n",
    "                    if not pmask >> j & 1:\n",
    "                        continue\n",
    "                    tmp = dp[j][pmask] + overlap[j][i]\n",
    "                    if tmp >= dp[i][mask]:\n",
    "                        dp[i][mask] = tmp\n",
    "                        pa[i][mask] = j\n",
    "                \n",
    "        mask = m - 1\n",
    "        idx = 0\n",
    "        for i in range(n):\n",
    "            if dp[i][mask] > dp[idx][mask]:\n",
    "                idx = i\n",
    "                \n",
    "        ans = ''\n",
    "        nxt = -1\n",
    "        while mask:\n",
    "            if nxt == -1:\n",
    "                ans = words[idx]\n",
    "            else:\n",
    "                ans = words[idx][:len(words[idx])-overlap[idx][nxt]] + ans\n",
    "            nxt = idx\n",
    "            idx = pa[idx][mask]\n",
    "            mask ^= 1 << nxt\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get(self, a, b):\n",
    "        for i in range(min(len(a), len(b)), 0, -1):\n",
    "            if a[len(a) - i:] == b[:i]:\n",
    "                return i\n",
    "        return 0\n",
    "\n",
    "    def shortestSuperstring(self, words):\n",
    "        n = len(words)\n",
    "        tr = [[self.get(words[i], words[j]) for j in range(n)] for i in range(n)]\n",
    "\n",
    "        INF = 1e8\n",
    "        f = [[INF] * n for _ in range(1 << n)]\n",
    "        for i in range(n):\n",
    "            f[1 << i][i] = len(words[i])\n",
    "\n",
    "        for i in range(1 << n):\n",
    "            for j in range(n):\n",
    "                if f[i][j] == INF:\n",
    "                    continue\n",
    "                for k in range(n):\n",
    "                    if not (i >> k & 1):\n",
    "                        f[i | (1 << k)][k] = min(f[i | (1 << k)][k], f[i][j] + len(words[k]) - tr[j][k])\n",
    "\n",
    "        i = (1 << n) - 1\n",
    "        j = 0\n",
    "        for k in range(n):\n",
    "            if f[i][k] < f[i][j]:\n",
    "                j = k\n",
    "\n",
    "        q = []\n",
    "        for u in range(n):\n",
    "            q.append(j)\n",
    "            for k in range(n):\n",
    "                if f[i - (1 << j)][k] + len(words[j]) - tr[k][j] == f[i][j]:\n",
    "                    i -= 1 << j\n",
    "                    j = k\n",
    "                    break\n",
    "\n",
    "        q.reverse()\n",
    "        res = words[q[0]]\n",
    "        for i in range(1, n):\n",
    "            res += words[q[i]][tr[q[i - 1]][q[i]]:]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        overlap = [[0] * n for _ in range(n)]\n",
    "        for i, word1 in enumerate(words):\n",
    "            for j, word2 in enumerate(words):\n",
    "                for k in range(min(len(word1), len(word2)), 0, -1):\n",
    "                    if word1[-k:] == word2[:k]:\n",
    "                        overlap[i][j] = k\n",
    "                        break\n",
    "\n",
    "        # 从之前的状态转移而来\n",
    "        n = len(words)\n",
    "        m = 1 << n\n",
    "        dp = [[0] * m for _ in range(n)]\n",
    "        pa = [[0] * m for _ in range(n)]\n",
    "        for mask in range(1, m):\n",
    "            for i in range(n):\n",
    "                if not mask >> i & 1:\n",
    "                    continue\n",
    "                pre = mask ^ (1 << i)\n",
    "                for j in range(n):\n",
    "                    if not pre >> j & 1:\n",
    "                        continue\n",
    "                    tmp = dp[j][pre] + overlap[j][i]\n",
    "                    if tmp >= dp[i][mask]:\n",
    "                        dp[i][mask] = tmp\n",
    "                        pa[i][mask] = j\n",
    "                \n",
    "        mask = m - 1\n",
    "        idx = 0\n",
    "        for i in range(n):\n",
    "            if dp[i][mask] > dp[idx][mask]:\n",
    "                idx = i\n",
    "                \n",
    "        ans = words[idx]\n",
    "        while True:\n",
    "            nxt = idx\n",
    "            idx = pa[idx][mask]\n",
    "            mask ^= 1 << nxt\n",
    "            if not mask:\n",
    "                break\n",
    "            ans = words[idx][:len(words[idx])-overlap[idx][nxt]] + ans\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        overlap = [[0] * n for _ in range(n)]\n",
    "        for i, word1 in enumerate(words):\n",
    "            for j, word2 in enumerate(words):\n",
    "                for k in range(min(len(word1), len(word2)), 0, -1):\n",
    "                    if word1[-k:] == word2[:k]:\n",
    "                        overlap[i][j] = k\n",
    "                        break\n",
    "\n",
    "        m = 1 << n\n",
    "        dp = [[0] * m for _ in range(n)]  # 最大重叠长度之和\n",
    "        pa = [[0] * m for _ in range(n)]\n",
    "        for mask in range(1, m):\n",
    "            for i in range(n):\n",
    "                if not mask >> i & 1:\n",
    "                    continue\n",
    "                pmask = mask ^ (1 << i)\n",
    "                for j in range(n):\n",
    "                    if not pmask >> j & 1:\n",
    "                        continue\n",
    "                    tmp = dp[j][pmask] + overlap[j][i]\n",
    "                    if tmp >= dp[i][mask]:\n",
    "                        dp[i][mask] = tmp\n",
    "                        pa[i][mask] = j\n",
    "                \n",
    "        mask = m - 1\n",
    "        idx = 0\n",
    "        for i in range(n):\n",
    "            if dp[i][mask] > dp[idx][mask]:\n",
    "                idx = i\n",
    "                \n",
    "        ans = words[idx]\n",
    "        while True:\n",
    "            nxt = idx\n",
    "            idx = pa[idx][mask]\n",
    "            mask ^= 1 << nxt\n",
    "            if not mask:\n",
    "                break\n",
    "            ans = words[idx][:len(words[idx])-overlap[idx][nxt]] + ans\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get(self, a, b):\n",
    "        for i in range(min(len(a), len(b)), 0, -1):\n",
    "            if a[len(a) - i:] == b[:i]:\n",
    "                return i\n",
    "        return 0\n",
    "\n",
    "    def shortestSuperstring(self, words):\n",
    "        n = len(words)\n",
    "        tr = [[self.get(words[i], words[j]) for j in range(n)] for i in range(n)]\n",
    "        u = 1 << n\n",
    "        f = [[inf] * n for _ in range(u)]\n",
    "        for i in range(n): f[1 << i][i] = len(words[i])\n",
    "        for i in range(u):\n",
    "            for j in range(n):\n",
    "                if f[i][j] == inf:continue\n",
    "                for k in range(n):\n",
    "                    if not (i >> k & 1):\n",
    "                        f[i | (1 << k)][k] = min(f[i | (1 << k)][k], f[i][j] + len(words[k]) - tr[j][k])\n",
    "        #print(min(f[-1]))\n",
    "        i = u - 1\n",
    "        j = 0\n",
    "        ans = []\n",
    "        for k in range(1, n):\n",
    "            if f[i][k] < f[i][j]:\n",
    "                j = k\n",
    "        \n",
    "        for _ in range(n):\n",
    "            ans.append(j)\n",
    "            for k in range(n):\n",
    "                if f[i - (1 << j)][k] + len(words[j]) - tr[k][j] == f[i][j]:\n",
    "                    i -= 1 << j\n",
    "                    j = k\n",
    "                    \n",
    "                    break\n",
    "        ans.reverse()\n",
    "        print(ans)\n",
    "        res = words[ans[0]]\n",
    "        for i in range(1, len(ans)):\n",
    "            res += words[ans[i]][tr[ans[i - 1]][ans[i]]: ]\n",
    "        #     for k in range(n):\n",
    "        #     if f[i][k] < f[i][j]:\n",
    "        #         j = k\n",
    "\n",
    "        # q = []\n",
    "        # for u in range(n):\n",
    "        #     q.append(j)\n",
    "        #     for k in range(n):\n",
    "        #         if f[i - (1 << j)][k] + len(words[j]) - tr[k][j] == f[i][j]:\n",
    "        #             i -= 1 << j\n",
    "        #             j = k\n",
    "        #             break\n",
    "\n",
    "        # q.reverse()\n",
    "        # res = words[q[0]]\n",
    "        # for i in range(1, n):\n",
    "        #     res += words[q[i]][tr[q[i - 1]][q[i]]:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "设 dp(mask, i) 表示已经选出的字符串为 mask（mask 是一个长度为 A.length 的二进制数，\n",
    "它的第 k 位如果为 1，则表示第 k 个字符串已经选出，否则表示第 k 个字符串没有被选出），\n",
    "且最后一个选出的字符串是 A[i] 时的重复部分的最大长度。在状态转移时，\n",
    "我们枚举下一个选出的字符串 j，就有 dp(mask ^ (1 << j), j) = max{overlap(A[i], A[j]) + dp(mask, i)}\n",
    "当然 dp(mask, i) 只记录了重复部分的最大长度，要得到这个最大长度对应的字符串，\n",
    "我们还需要记录一下每个状态从哪个状态转移得来，最后通过逆推的方式还原这个字符串。\n",
    "'''\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, A: List[str]) -> str:\n",
    "        N = len(A)\n",
    "\n",
    "        # Populate overlaps\n",
    "        overlaps = [[0] * N for _ in range(N)]\n",
    "        for i, x in enumerate(A):\n",
    "            for j, y in enumerate(A):\n",
    "                if i != j:\n",
    "                    for ans in range(min(len(x), len(y)), -1, -1):\n",
    "                        if x.endswith(y[:ans]):\n",
    "                            overlaps[i][j] = ans\n",
    "                            break\n",
    "\n",
    "        # dp[mask][i] = most overlap with mask, ending with ith element\n",
    "        dp = [[0] * N for _ in range(1<<N)]\n",
    "        parent = [[None] * N for _ in range(1<<N)]\n",
    "        for mask in range(1, 1 << N):\n",
    "            for bit in range(N):\n",
    "                if (mask >> bit) & 1:\n",
    "                    # Let's try to find dp[mask][bit].  Previously, we had\n",
    "                    # a collection of items represented by pmask.\n",
    "                    pmask = mask ^ (1 << bit)\n",
    "                    if pmask == 0: continue\n",
    "                    for i in range(N):\n",
    "                        if (pmask >> i) & 1:\n",
    "                            # For each bit i in pmask, calculate the value\n",
    "                            # if we ended with word i, then added word 'bit'.\n",
    "                            value = dp[pmask][i] + overlaps[i][bit]\n",
    "                            if value > dp[mask][bit]:\n",
    "                                dp[mask][bit] = value\n",
    "                                parent[mask][bit] = i\n",
    "\n",
    "        # Answer will have length sum(len(A[i]) for i) - max(dp[-1])\n",
    "        # Reconstruct answer:\n",
    "\n",
    "        # Follow parents down backwards path that retains maximum overlap\n",
    "        perm = []\n",
    "        mask = (1<<N) - 1\n",
    "        i = max(range(N), key = dp[-1].__getitem__)\n",
    "        while i is not None:\n",
    "            perm.append(i)\n",
    "            mask, i = mask ^ (1<<i), parent[mask][i]\n",
    "\n",
    "        # Reverse path to get forwards direction; add all remaining words\n",
    "        perm = perm[::-1]\n",
    "        seen = [False] * N\n",
    "        for x in perm:\n",
    "            seen[x] = True\n",
    "        perm.extend([i for i in range(N) if not seen[i]])\n",
    "\n",
    "        # Reconstruct answer given perm = word indices in left to right order\n",
    "        ans = [A[perm[0]]]\n",
    "        for i in range(1, len(perm)):\n",
    "            overlap = overlaps[perm[i-1]][perm[i]]\n",
    "            ans.append(A[perm[i]][overlap:])\n",
    "\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        mask = 1<<n\n",
    "        g = [[0]*n for _ in range(n)] # g[i][j]表示words[i]后缀和words[j]前缀重合的最大长度\n",
    "        for i,x in enumerate(words):\n",
    "            for j,y in enumerate(words):\n",
    "                for L in range(min(len(x),len(y)),0,-1):\n",
    "                    if x[-L:] == y[:L]:\n",
    "                        g[i][j] = L\n",
    "                        break\n",
    "\n",
    "        f = [[0]*n for _ in range(mask)] # f[i][j]状态为i，最后一个使用的是j，前后缀重合的总长度\n",
    "        p = [[0]*n for _ in range(mask)] # p[i][j] 状态为i，最后一个使用的是j，前一个使用的word，用来求最终结果\n",
    "        for s in range(mask):#words中单词使用状态,第i为位1代表已经使用\n",
    "            for i,x in enumerate(words):\n",
    "                if (s >> i) & 1 == 0:\n",
    "                    continue\n",
    "                for j,y in enumerate(words):\n",
    "                    if (s >> j) & 1:\n",
    "                        continue\n",
    "                    # i已经用了，j还没用的情况进行转移,把j拼接上去,目标是让重合长度最大，最后的超级子串最短\n",
    "                    if f[s|(1 << j)][j] <= f[s][i] + g[i][j]:\n",
    "                        f[s|(1 << j)][j] = f[s][i] + g[i][j]\n",
    "                        p[s|(1 << j)][j] = i\n",
    "\n",
    "        # 求最后一个被使用的单词\n",
    "        mx = f[mask - 1][0]\n",
    "        idx = 0\n",
    "        for i in range(1,n):\n",
    "            if f[mask - 1][i] > mx:\n",
    "                mx = f[mask - 1][i]\n",
    "                idx = i\n",
    "        # 根据p倒推答案\n",
    "        ans = ''\n",
    "        s = mask - 1\n",
    "        last = -1\n",
    "        while s:\n",
    "            w = words[idx]\n",
    "            if last == -1:\n",
    "                ans = w\n",
    "            else:\n",
    "                ans = w[:len(w) - g[idx][last]] + ans\n",
    "            last = idx\n",
    "            idx = p[s][idx]\n",
    "            s ^= (1 << last)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "\n",
    "        def prefix_function(s):\n",
    "            n = len(s)\n",
    "            pi = [0] * n\n",
    "            for i in range(1, n):\n",
    "                j = pi[i - 1]\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = pi[j - 1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                pi[i] = j\n",
    "            return pi[-1]\n",
    "\n",
    "        for i, s in enumerate(words):\n",
    "            for j, t in enumerate(words):\n",
    "                if i == j: continue\n",
    "                g[i][j] = prefix_function(t + \"#\" + s)\n",
    "                # for l in range(min(len(s), len(t)), 0, -1):\n",
    "                #     if s[-l:] == t[:l]:\n",
    "                #         g[i][j] = l\n",
    "                #         break\n",
    "                        \n",
    "        dp = [[0] * n for _ in range(1 << n)]\n",
    "        p = [[0] * n for _ in range(1 << n)]\n",
    "        for mask in range(1, 1 << n):\n",
    "            for i in range(n):\n",
    "                if not (mask >> i) & 1:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if (mask >> j) & 1:\n",
    "                        continue\n",
    "                    if dp[mask | (1 << j)][j] <= dp[mask][i] + g[i][j]:\n",
    "                        dp[mask | (1 << j)][j] = dp[mask][i] + g[i][j]\n",
    "                        p[mask | (1 << j)][j] = i\n",
    "\n",
    "        mx, idx, last, status = dp[-1][0], 0, -1, (1 << n) - 1\n",
    "        for i in range(1, n):\n",
    "            if dp[-1][i] > mx:\n",
    "                mx, idx = dp[-1][i], i\n",
    "                \n",
    "        ans = \"\"\n",
    "        while status:\n",
    "            if last == -1:\n",
    "                ans = words[idx]\n",
    "            else:\n",
    "                ans = words[idx][:len(words[idx])-g[idx][last]] + ans\n",
    "            last = idx\n",
    "            idx = p[status][idx]\n",
    "            status ^= 1 << last\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def overlap(self, a, b):\n",
    "        na, nb = len(a), len(b)\n",
    "        for i in range(min(na, nb), 0, -1):\n",
    "            if a[na-i:] == b[0:i]:\n",
    "                return i\n",
    "        return 0\n",
    "\n",
    "    def shortestSuperstring(self, A: List[str]) -> str:\n",
    "        INF = 0x3f3f3f3f\n",
    "        n= len(A)\n",
    "        M = 1<<n\n",
    "        o = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                o[i][j] = self.overlap(A[i], A[j])\n",
    "        dp = [[INF] * n for _ in range(M)]\n",
    "        path = [[0] * n for _ in range(M)]\n",
    "        for i in range(n):\n",
    "            dp[1<<i][i] = len(A[i])\n",
    "        for s in range(M):\n",
    "            for i in range(n):\n",
    "                if s^(1<<i) == 0:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if i != j and ((s>>j)&1):\n",
    "                        if dp[s][i] > dp[s^(1<<i)][j]+len(A[i])-o[j][i]:\n",
    "                            dp[s][i] = dp[s^(1<<i)][j]+len(A[i])-o[j][i]\n",
    "                            path[s][i] = j\n",
    "        last = 0\n",
    "        for i in range(1, n):\n",
    "            if dp[M-1][i] < dp[M-1][last]:\n",
    "                last = i\n",
    "        seq = [last]\n",
    "        s = M - 1\n",
    "        for _ in range(n-1):\n",
    "            tmp = last\n",
    "            last = path[s][last]\n",
    "            seq.append(last)\n",
    "            s = s^(1<<tmp)\n",
    "        seq = seq[::-1]\n",
    "        res = A[seq[0]]\n",
    "        for i in range(1, n):\n",
    "            res += A[seq[i]][o[seq[i-1]][seq[i]]:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "\n",
    "        \n",
    "        N = len(words)\n",
    "\n",
    "        # Populate overlaps \n",
    "        overlaps = [[0]* N for _ in range(N)]\n",
    "        for i,x in enumerate(words):\n",
    "            for j,y in enumerate(words):\n",
    "                if i==j:\n",
    "                    continue\n",
    "                for cut in range(min(len(x), len(y)), 0, -1):\n",
    "                    if x[-cut:] == y[:cut]:\n",
    "                        overlaps[i][j] = cut \n",
    "                        break\n",
    "\n",
    "        dp = [[0]*N for _ in range(1<<N)]\n",
    "        parent = [[None]*N for _ in range(1<<N)]\n",
    "        for mask in range(1, 1<<N):\n",
    "            for bit in range(N):\n",
    "                if (mask>>bit) & 1:\n",
    "                    previous_mask = mask ^ (1<<bit)\n",
    "                    if previous_mask==0:\n",
    "\n",
    "                        continue\n",
    "                    for i in range(N):\n",
    "                        if (previous_mask>>i)&1:\n",
    "                            value = dp[previous_mask][i]+overlaps[i][bit]\n",
    "                            if value>dp[mask][bit]:\n",
    "                                dp[mask][bit] = value \n",
    "                                parent[mask][bit] = i \n",
    "        \n",
    "        # reconstruct answer \n",
    "        index, largest = -1, -1\n",
    "        for i in range(N):\n",
    "            if dp[(1<<N)-1][i]>largest:\n",
    "                largest = dp[(1<<N)-1][i]\n",
    "                index = i \n",
    "        perm = []\n",
    "        i = index\n",
    "        while i is not None:\n",
    "            perm.append(i)\n",
    "            mask,i = mask^(1<<i), parent[mask][i]\n",
    "        \n",
    "        for i in range(N):\n",
    "            if i not in perm:\n",
    "                perm.append(i)\n",
    "        perm = perm[::-1]\n",
    "\n",
    "        ans = [words[perm[0]]]\n",
    "        for i in range(1, len(perm)):\n",
    "            overlap = overlaps[perm[i-1]][perm[i]]\n",
    "            ans.append(words[perm[i]][overlap:] )\n",
    "        return \"\".join(ans)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, ws: List[str]) -> str:\n",
    "        #用过为1，没用过为0\n",
    "        n=len(ws)\n",
    "        g=[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                len1=len(ws[i])\n",
    "                len2=len(ws[j])\n",
    "                lenth=min(len1,len2)\n",
    "                for k in range(lenth,0,-1):\n",
    "                    if ws[i][len1-k:]==ws[j][:k]:\n",
    "                        g[i][j]=k\n",
    "                        break\n",
    "        mask=1<<n\n",
    "        f=[[0]*n for _ in range(mask)]\n",
    "        p=[[0]*n for _ in range(mask)]\n",
    "        for s in range(mask):\n",
    "            for i in range(n):\n",
    "                if (s>>i)&1 == 0:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if (s>>j)&1 == 1:\n",
    "                        continue\n",
    "                    nexmask=s|(1<<j)\n",
    "                    if f[nexmask][j]<=f[s][i]+g[i][j]:\n",
    "                        f[nexmask][j]=f[s][i]+g[i][j]\n",
    "                        p[nexmask][j]=i\n",
    "        idx,last,mask=0,-1,(1<<n)-1\n",
    "        max_val=f[mask][0]\n",
    "        for i in range(1,n):\n",
    "            if f[mask][i]>max_val:\n",
    "                idx=i\n",
    "                max_val=f[mask][i]\n",
    "        ans=\"\"\n",
    "        state=mask\n",
    "        while state != 0:\n",
    "            if last==-1:\n",
    "                ans=ws[idx]\n",
    "            else:\n",
    "                ans=ws[idx][:len(ws[idx])-g[idx][last]]+ans\n",
    "            last=idx\n",
    "            idx=p[state][idx]\n",
    "            state^=1<<last\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        mask = 1<<n\n",
    "        g = [[0]*n for _ in range(n)] # g[i][j]表示words[i]后缀和words[j]前缀重合的最大长度\n",
    "        for i,x in enumerate(words):\n",
    "            for j,y in enumerate(words):\n",
    "                for L in range(min(len(x),len(y)),0,-1):\n",
    "                    if x[-L:] == y[:L]:\n",
    "                        g[i][j] = L\n",
    "                        break\n",
    "\n",
    "        f = [[0]*n for _ in range(mask)] # f[i][j]状态为i，最后一个使用的是j，前后缀重合的总长度\n",
    "        p = [[0]*n for _ in range(mask)] # p[i][j] 状态为i，最后一个使用的是j，前一个使用的word，用来求最终结果\n",
    "        for s in range(mask):#words中单词使用状态,第i为位1代表已经使用\n",
    "            for i,x in enumerate(words):\n",
    "                if (s >> i) & 1 == 0:\n",
    "                    continue\n",
    "                for j,y in enumerate(words):\n",
    "                    if (s >> j) & 1:\n",
    "                        continue\n",
    "                    # i已经用了，j还没用的情况进行转移,把j拼接上去,目标是让重合长度最大，最后的超级子串最短\n",
    "                    if f[s|(1 << j)][j] <= f[s][i] + g[i][j]:\n",
    "                        f[s|(1 << j)][j] = f[s][i] + g[i][j]\n",
    "                        p[s|(1 << j)][j] = i\n",
    "\n",
    "        # 求最后一个被使用的单词\n",
    "        mx = f[mask - 1][0]\n",
    "        idx = 0\n",
    "        for i in range(1,n):\n",
    "            if f[mask - 1][i] > mx:\n",
    "                mx = f[mask - 1][i]\n",
    "                idx = i\n",
    "        # 根据p倒推答案\n",
    "        ans = ''\n",
    "        s = mask - 1\n",
    "        last = -1\n",
    "        while s:\n",
    "            w = words[idx]\n",
    "            if last == -1:\n",
    "                ans = w\n",
    "            else:\n",
    "                ans = w[:len(w) - g[idx][last]] + ans\n",
    "            last = idx\n",
    "            idx = p[s][idx]\n",
    "            s ^= (1 << last)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        mask = (1<<n)\n",
    "\n",
    "        g = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j: continue \n",
    "                a, b = words[i], words[j]\n",
    "                k = min(len(a), len(b))\n",
    "                ma = 0\n",
    "                for t in range(k, 0, -1):\n",
    "                    if a[len(a)-t:] == b[:t]:\n",
    "                        ma = t \n",
    "                        break \n",
    "                g[i][j] = ma \n",
    "        f = [[0 for _ in range(n)] for _ in range(mask)]\n",
    "        p = [[0 for _ in range(n)] for _ in range(mask)]\n",
    "\n",
    "        for s in range(mask):\n",
    "            for i in range(n):\n",
    "                if (s >> i) & 1 == 0:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if (s >> j) & 1 == 1:\n",
    "                        continue\n",
    "                    if f[s | (1 << j)][j] <= f[s][i] + g[i][j]:\n",
    "                        f[s | (1 << j)][j] = f[s][i] + g[i][j]\n",
    "                        p[s | (1 << j)][j] = i\n",
    "        \n",
    "        max_val = f[mask - 1][0]\n",
    "        idx, last, status = 0, -1, mask - 1        \n",
    "        for i in range(1, n):\n",
    "            if max_val < f[mask - 1][i]:\n",
    "                max_val = f[mask - 1][i]\n",
    "                idx = i\n",
    "        ans = \"\"\n",
    "        while status != 0:\n",
    "            if last == -1:\n",
    "                ans = words[idx]\n",
    "            else:\n",
    "                ans = words[idx][:len(words[idx]) - g[idx][last]] + ans\n",
    "            last = idx\n",
    "            idx = p[status][idx]\n",
    "            status ^= 1 << last\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        \"\"\"\n",
    "        预处理每个字符的重叠部分\n",
    "        用dp求最长重叠，那么实际上len-重叠=最短字符串\n",
    "        同时需要记录每个状态的前驱结点\n",
    "        最后从后往前构造答案\n",
    "        \"\"\"\n",
    "        n = len(words)\n",
    "        m = 1 << n \n",
    "\n",
    "        g = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                a, b = words[i], words[j]\n",
    "                mi = min(len(a), len(b))\n",
    "                for k in range(mi, 0, -1):\n",
    "                    if a[len(a)-k:] == b[:k]:\n",
    "                        g[i][j] = k \n",
    "                        break \n",
    "        \n",
    "        # dp求最大重叠长度\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        pre = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1 == 0: continue \n",
    "                pmask = i ^ (1 << j)\n",
    "                for k in range(n):\n",
    "                    if (pmask >> k) & 1 == 0: continue\n",
    "                    if dp[i][j] <= dp[pmask][k] + g[k][j]:\n",
    "                        dp[i][j] = dp[pmask][k] + g[k][j]\n",
    "                        pre[i][j] = k \n",
    "\n",
    "        ans = \"\"\n",
    "        idx = 0\n",
    "        ma = -1\n",
    "        for i in range(n):\n",
    "            if ma < dp[-1][i]:\n",
    "                ma = dp[-1][i]\n",
    "                idx = i \n",
    "        \n",
    "        last = -1\n",
    "        mask = m-1\n",
    "        while mask != 0:\n",
    "            if last == -1:\n",
    "                ans = words[idx]\n",
    "            else:\n",
    "                ans = words[idx][:len(words[idx])-g[idx][last]] + ans \n",
    "            last = idx\n",
    "            idx = pre[mask][idx]\n",
    "            mask ^= (1 << last)\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i, s in enumerate(words):\n",
    "            for j, t in enumerate(words):\n",
    "                if s == t: continue\n",
    "                for l in range(min(len(s), len(t)), 0, -1):\n",
    "                    if s[-l:] == t[:l]:\n",
    "                        g[i][j] = l\n",
    "                        break\n",
    "                        \n",
    "        dp = [[0] * n for _ in range(1 << n)]\n",
    "        p = [[0] * n for _ in range(1 << n)]\n",
    "        for mask in range(1, 1 << n):\n",
    "            for i in range(n):\n",
    "                if not (mask >> i) & 1:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if (mask >> j) & 1:\n",
    "                        continue\n",
    "                    if dp[mask | (1 << j)][j] <= dp[mask][i] + g[i][j]:\n",
    "                        dp[mask | (1 << j)][j] = dp[mask][i] + g[i][j]\n",
    "                        p[mask | (1 << j)][j] = i\n",
    "\n",
    "        mx, idx, last, status = dp[-1][0], 0, -1, (1 << n) - 1\n",
    "        for i in range(1, n):\n",
    "            if dp[-1][i] > mx:\n",
    "                mx, idx = dp[-1][i], i\n",
    "                \n",
    "        ans = \"\"\n",
    "        while status:\n",
    "            if last == -1:\n",
    "                ans = words[idx]\n",
    "            else:\n",
    "                ans = words[idx][:len(words[idx])-g[idx][last]] + ans\n",
    "            last = idx\n",
    "            idx = p[status][idx]\n",
    "            status ^= 1 << last\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        mask = (1<<n)\n",
    "\n",
    "        g = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j: continue \n",
    "                a, b = words[i], words[j]\n",
    "                k = min(len(a), len(b))\n",
    "                ma = 0\n",
    "                for t in range(k):\n",
    "                    if a[len(a)-t-1:] == b[:t+1]:\n",
    "                        ma = t+1 \n",
    "                g[i][j] = ma \n",
    "        f = [[0 for _ in range(n)] for _ in range(mask)]\n",
    "        p = [[0 for _ in range(n)] for _ in range(mask)]\n",
    "\n",
    "        for s in range(mask):\n",
    "            for i in range(n):\n",
    "                if (s >> i) & 1 == 0:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if (s >> j) & 1 == 1:\n",
    "                        continue\n",
    "                    if f[s | (1 << j)][j] <= f[s][i] + g[i][j]:\n",
    "                        f[s | (1 << j)][j] = f[s][i] + g[i][j]\n",
    "                        p[s | (1 << j)][j] = i\n",
    "        \n",
    "        max_val = f[mask - 1][0]\n",
    "        idx, last, status = 0, -1, mask - 1        \n",
    "        for i in range(1, n):\n",
    "            if max_val < f[mask - 1][i]:\n",
    "                max_val = f[mask - 1][i]\n",
    "                idx = i\n",
    "        ans = \"\"\n",
    "        while status != 0:\n",
    "            if last == -1:\n",
    "                ans = words[idx]\n",
    "            else:\n",
    "                ans = words[idx][:len(words[idx]) - g[idx][last]] + ans\n",
    "            last = idx\n",
    "            idx = p[status][idx]\n",
    "            status ^= 1 << last\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, ws: List[str]) -> str:\n",
    "        n, mask = len(ws), 1 << len(ws)\n",
    "        g = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                a, b = ws[i], ws[j]\n",
    "                l1, l2 = len(a), len(b)\n",
    "                length = min(l1, l2)\n",
    "                for k in range(length, 0, -1):\n",
    "                    if a[l1 - k:] == b[:k]:\n",
    "                        g[i][j] = k\n",
    "                        break\n",
    "        f = [[0 for _ in range(n)] for _ in range(mask)]\n",
    "        p = [[0 for _ in range(n)] for _ in range(mask)]\n",
    "        for s in range(mask):\n",
    "            for i in range(n):\n",
    "                if (s >> i) & 1 == 0:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if (s >> j) & 1 == 1:\n",
    "                        continue\n",
    "                    if f[s | (1 << j)][j] <= f[s][i] + g[i][j]:\n",
    "                        f[s | (1 << j)][j] = f[s][i] + g[i][j]\n",
    "                        p[s | (1 << j)][j] = i\n",
    "        \n",
    "        max_val = f[mask - 1][0]\n",
    "        idx, last, status = 0, -1, mask - 1        \n",
    "        for i in range(1, n):\n",
    "            if max_val < f[mask - 1][i]:\n",
    "                max_val = f[mask - 1][i]\n",
    "                idx = i\n",
    "        ans = \"\"\n",
    "        while status != 0:\n",
    "            if last == -1:\n",
    "                ans = ws[idx]\n",
    "            else:\n",
    "                ans = ws[idx][:len(ws[idx]) - g[idx][last]] + ans\n",
    "            last = idx\n",
    "            idx = p[status][idx]\n",
    "            status ^= 1 << last\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n, mask = len(words), 1 << len(words)\n",
    "        g = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                a, b = words[i], words[j]\n",
    "                l1, l2 = len(a), len(b)\n",
    "                length = min(l1, l2)\n",
    "                for k in range(length, 0, -1):\n",
    "                    if a[l1 - k:] == b[:k]:\n",
    "                        g[i][j] = k\n",
    "                        break\n",
    "        f = [[0 for _ in range(n)] for _ in range(mask)]\n",
    "        p = [[0 for _ in range(n)] for _ in range(mask)]\n",
    "        for s in range(mask):\n",
    "            for i in range(n):\n",
    "                if (s >> i) & 1 == 0:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if (s >> j) & 1 == 1:\n",
    "                        continue\n",
    "                    if f[s | (1 << j)][j] <= f[s][i] + g[i][j]:\n",
    "                        f[s | (1 << j)][j] = f[s][i] + g[i][j]\n",
    "                        p[s | (1 << j)][j] = i\n",
    "        \n",
    "        max_val = f[mask - 1][0]\n",
    "        idx, last, status = 0, -1, mask - 1        \n",
    "        for i in range(1, n):\n",
    "            if max_val < f[mask - 1][i]:\n",
    "                max_val = f[mask - 1][i]\n",
    "                idx = i\n",
    "        ans = \"\"\n",
    "        while status != 0:\n",
    "            if last == -1:\n",
    "                ans = words[idx]\n",
    "            else:\n",
    "                ans = words[idx][:len(words[idx]) - g[idx][last]] + ans\n",
    "            last = idx\n",
    "            idx = p[status][idx]\n",
    "            status ^= 1 << last\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, ws: List[str]) -> str:\n",
    "        n, mask = len(ws), 1 << len(ws)\n",
    "        g = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                a, b = ws[i], ws[j]\n",
    "                l1, l2 = len(a), len(b)\n",
    "                length = min(l1, l2)\n",
    "                for k in range(length, 0, -1):\n",
    "                    if a[l1 - k:] == b[:k]:\n",
    "                        g[i][j] = k\n",
    "                        break\n",
    "        f = [[0 for _ in range(n)] for _ in range(mask)]\n",
    "        p = [[0 for _ in range(n)] for _ in range(mask)]\n",
    "        for s in range(mask):\n",
    "            for i in range(n):\n",
    "                if (s >> i) & 1 == 0:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if (s >> j) & 1 == 1:\n",
    "                        continue\n",
    "                    if f[s | (1 << j)][j] <= f[s][i] + g[i][j]:\n",
    "                        f[s | (1 << j)][j] = f[s][i] + g[i][j]\n",
    "                        p[s | (1 << j)][j] = i\n",
    "        \n",
    "        max_val = f[mask - 1][0]\n",
    "        idx, last, status = 0, -1, mask - 1        \n",
    "        for i in range(1, n):\n",
    "            if max_val < f[mask - 1][i]:\n",
    "                max_val = f[mask - 1][i]\n",
    "                idx = i\n",
    "        ans = \"\"\n",
    "        while status != 0:\n",
    "            if last == -1:\n",
    "                ans = ws[idx]\n",
    "            else:\n",
    "                ans = ws[idx][:len(ws[idx]) - g[idx][last]] + ans\n",
    "            last = idx\n",
    "            idx = p[status][idx]\n",
    "            status ^= 1 << last\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "\n",
    "        graph = defaultdict(lambda :defaultdict(int))\n",
    "        n = len(words)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(len(words[i]),-1,-1):\n",
    "                    if words[j][:k] == words[i][-k:]:\n",
    "                        graph[i][j] = k\n",
    "                        break\n",
    "\n",
    "\n",
    "        def TSP(n):\n",
    "            dp = [[0 for _ in range(n)] for _ in range(1<<n)]\n",
    "            parents = [[-1 for _ in range(n)] for _ in range(1<<n)]\n",
    "            for state in range(1<<n):\n",
    "                for bit in range(n):\n",
    "                    if state & (1 << bit):\n",
    "                        p_state = state ^ (1 << bit)\n",
    "                        if p_state == 0:continue\n",
    "                        for i in range(n):\n",
    "                            if p_state & (1 << i):\n",
    "                                if dp[state][bit] < dp[p_state][i] + graph[i][bit]:\n",
    "                                    dp[state][bit] = dp[p_state][i] + graph[i][bit]\n",
    "                                    parents[state][bit] = i\n",
    "\n",
    "            i = max(range(n),key=dp[-1].__getitem__)\n",
    "            max_weight = dp[-1][i]\n",
    "            ans = []\n",
    "            state = 2 ** n - 1\n",
    "            while i != -1:\n",
    "                ans.append(i)\n",
    "                state , i = state ^ (1 << i) , parents[state][i]\n",
    "            ans = ans[::-1]\n",
    "            for i in range(n):\n",
    "                if i not in ans:\n",
    "                    ans.append(i)\n",
    "            return max_weight , ans\n",
    "\n",
    "        _ , path = TSP(n)\n",
    "\n",
    "        ans = words[path[0]]\n",
    "        for i in range(1,n):\n",
    "            word = words[path[i]]\n",
    "            ans += word[graph[path[i-1]][path[i]]:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        m = 1<<n\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        p = [[0]*n for _ in range(m)]\n",
    "        # 最长重叠字符串\n",
    "        g = [[0]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j: continue \n",
    "                a, b = words[i], words[j]\n",
    "                k = min(len(a), len(b))\n",
    "                for t in range(k, -1, -1):\n",
    "                    if a[len(a)-t:] == b[:t]:\n",
    "                        g[i][j] = t \n",
    "                        break \n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1 == 0: continue  # 确保之前已经挑选过j这个状态\n",
    "                for k in range(n):\n",
    "                    if (i >> k) & 1 == 1: continue # 确保之前没有选过k\n",
    "                    if dp[i | (1<<k)][k] <= dp[i][j] + g[j][k] :\n",
    "                        dp[i | (1<<k)][k] = dp[i][j] + g[j][k]\n",
    "                        p[i | (1<<k)][k] = j \n",
    "        \n",
    "        max_val = dp[m - 1][0]\n",
    "        idx = 0 \n",
    "        last = -1\n",
    "        for i in range(1, n):\n",
    "            if max_val < dp[m - 1][i]:\n",
    "                max_val = dp[m - 1][i]\n",
    "                idx = i\n",
    "\n",
    "        \n",
    "        ans = \"\"\n",
    "        mask = m - 1\n",
    "        while mask != 0:\n",
    "            if last == -1:\n",
    "                ans = words[idx]\n",
    "            else:\n",
    "                ans = words[idx][:len(words[idx]) - g[idx][last]] + ans\n",
    "            last = idx\n",
    "            idx = p[mask][idx]\n",
    "            mask ^= 1 << last\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        import itertools \n",
    "        N = len(words)\n",
    "        \n",
    "        overlaps = [[0] * N for _ in range(N)]\n",
    "        for i, j in itertools.product(range(N), range(N)):\n",
    "            x, y = words[i], words[j]\n",
    "            if x != y:\n",
    "                for ed in range(min(len(x), len(y)), 0, -1):\n",
    "                    if x.endswith(y[:ed]):\n",
    "                        overlaps[i][j] = ed\n",
    "                        break\n",
    "        \n",
    "        dp = [[0] * N for _  in range(1<<N)]\n",
    "        parent = [[None] * N for _ in range(1<<N)]\n",
    "        for mask in range(1, 1<<N):\n",
    "            for bit in range(N):\n",
    "                if (mask >> bit) & 1:\n",
    "                    pmask = mask ^ (1 << bit)\n",
    "                    if pmask == 0: continue\n",
    "                    for i in range(N):\n",
    "                        if (pmask >> i) & 1:\n",
    "                            value = dp[pmask][i] + overlaps[i][bit]\n",
    "                            if value >= dp[mask][bit]:\n",
    "                                dp[mask][bit] = value\n",
    "                                parent[mask][bit] = i\n",
    "        print(dp)\n",
    "        print(parent)\n",
    "\n",
    "        perm = []\n",
    "        mask = (1<<N)-1\n",
    "        i = max(range(N), key = lambda x: dp[mask][x])\n",
    "        print(i)\n",
    "        while mask != 0:\n",
    "            print([mask, i])\n",
    "            perm.append(i)\n",
    "            mask, i = mask ^ (1 << i), parent[mask][i]\n",
    "        perm.reverse()\n",
    "\n",
    "        res = words[perm[0]]\n",
    "        for i in range(1,len(perm)):\n",
    "            st = overlaps[perm[i-1]][perm[i]]\n",
    "            res += words[perm[i]][st:]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        common = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue \n",
    "                for k in range(min(len(words[i]), len(words[j])), 0, - 1):\n",
    "                    if words[i].endswith(words[j][:k]):\n",
    "                        common[i][j] = k \n",
    "                        break \n",
    "        m = 1 << n \n",
    "        dp = [['' for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            dp[1 << i][i] = words[i]\n",
    "        for i in range(1, m):\n",
    "            for cur in range(n):\n",
    "                if not i & 1 << cur:\n",
    "                    continue \n",
    "                for nxt in range(n):\n",
    "                    if i & 1 << nxt:\n",
    "                        continue \n",
    "                    if not dp[i | 1 << nxt][nxt] or len(dp[i | 1 << nxt][nxt]) > len(dp[i][cur]) + len(words[nxt]) - common[cur][nxt]:\n",
    "                        dp[i | 1 << nxt][nxt] = dp[i][cur] + words[nxt][common[cur][nxt] : ]\n",
    "        return min(dp[-1], key = len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        words.append(\"\")\n",
    "        n = len(words)\n",
    "        l = [len(w) for w in words]\n",
    "        d = [[0]*n for _ in range(n)]\n",
    "        for i,w in enumerate(words):\n",
    "            for j,v in enumerate(words):\n",
    "                m = min(len(w),len(v))\n",
    "                for k in range(m, 0, -1):\n",
    "                    if w[-k:] == v[:k]:\n",
    "                        d[i][j] = k\n",
    "                        break\n",
    "\n",
    "        @cache\n",
    "        def f(i, x):\n",
    "            if x == (1 << n)-1:\n",
    "                return 0, tuple()\n",
    "            ans = math.inf\n",
    "            for j in range(n):\n",
    "                if (1 << j) & x == 0:\n",
    "                    c, o = f(j, x | (1 << j))\n",
    "                    if c + l[j] - d[i][j] < ans:\n",
    "                        ans = c + l[j] - d[i][j]\n",
    "                        order = [j] + list(o)\n",
    "            return ans, tuple(order)\n",
    "\n",
    "        _, order = f(n-1, 1 << (n-1))\n",
    "        i0, ans = n-1, ''\n",
    "        for i in order:\n",
    "            ans += words[i][d[i0][i]:]\n",
    "            i0 = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, w: List[str]) -> str:\n",
    "        w = list(set(w))\n",
    "        n = len(w)\n",
    "        a = set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j:\n",
    "                    if w[i] in w[j]:\n",
    "                        a.add(w[i])\n",
    "        w = [j for j in w if j not in a]\n",
    "        def f(x, y):\n",
    "            # if x[-1]!=y[0]:\n",
    "            #     return 0 \n",
    "            ans = 0\n",
    "            for k in range(1, min(len(x), len(y)) + 1):\n",
    "                if x[-k:]==y[:k]:\n",
    "                    ans = max(ans, k)\n",
    "            return ans\n",
    "\n",
    "        g = {}\n",
    "        a = {}\n",
    "        n = len(w)\n",
    "        for i in range(-1, n):\n",
    "            for j in range(n):\n",
    "                if i==(-1):\n",
    "                    g[(i, j)] = 0\n",
    "                    a[(i, j)] = w[j]\n",
    "                else:\n",
    "                    g[(i, j)] = f(w[i], w[j])\n",
    "                    a[(i, j)] = w[j][g[(i, j)]:]\n",
    "        \n",
    "\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            if x==0:\n",
    "                return [0, [y]]\n",
    "            else:\n",
    "                dis = {}\n",
    "                for j in range(n):\n",
    "                    if (x>>j)&1:\n",
    "                        tmp = dfs(x^(1<<j), j) \n",
    "                        dis[tmp[0] + g[(y, j)]] = [y] + tmp[1]\n",
    "                tmp = max(dis.keys())\n",
    "                return [tmp, dis[tmp][:]]\n",
    "        tmp = dfs((1<<n)-1, -1)[1]\n",
    "        ans = ''\n",
    "        print(w, tmp,g)\n",
    "        for j in range(len(tmp))[1:]:\n",
    "            x = tmp[j-1]\n",
    "            y = tmp[j]\n",
    "            s = a[(x, y)]\n",
    "            ans += s\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        m = 1 << n\n",
    "\n",
    "        g = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                a, b = words[i], words[j]\n",
    "                t = min(len(a), len(b))\n",
    "                for k in range(t, 0, -1):\n",
    "                    if a[len(a)-k:] == b[:k]:\n",
    "                        g[i][j] = k \n",
    "                        break \n",
    "        p = [[0]*n for _ in range(m)]\n",
    "        @cache\n",
    "        def dfs(mask, i):\n",
    "            if mask == m-1: return 0\n",
    "            res = 0\n",
    "            if i == -1:\n",
    "                # 一个字符串都没选的时候\n",
    "                for j in range(n):\n",
    "                    res = max(res, dfs(mask^(1<<j), j) + g[j][j])\n",
    "            else:\n",
    "                # 选一个没选过的字符串\n",
    "                for j in range(n):\n",
    "                    if (mask >> j) & 1 == 1: continue \n",
    "                    nxt = dfs(mask|(1<<j), j) + g[i][j]\n",
    "                    if res <= nxt:\n",
    "                        res = nxt\n",
    "                        p[mask][i] = j \n",
    "            \n",
    "            return res \n",
    "        \n",
    "        dfs(0, -1)\n",
    "\n",
    "        mask = 0\n",
    "        ma = 0\n",
    "        idx = 0\n",
    "        for i in range(n):\n",
    "            if ma < dfs(1<<i, i):\n",
    "                ma = dfs(1<<i, i)\n",
    "                idx = i \n",
    "\n",
    "        ans = \"\"\n",
    "        last = -1\n",
    "        mask = 0\n",
    "\n",
    "        while mask != m-1:\n",
    "            if last == -1:\n",
    "                ans = words[idx]\n",
    "            else:\n",
    "                ans += words[idx][g[last][idx]:]\n",
    "            last = idx \n",
    "            mask |= 1 << last\n",
    "            idx = p[mask][last]\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        @cache\n",
    "        def concat(a, b):\n",
    "            for i in range(0, len(words[a])):\n",
    "                if words[a][i:] == words[b][:len(words[a])-i]:\n",
    "                    return words[b][len(words[a])-i:]\n",
    "            return words[b]\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            ans = [''] * len(words)\n",
    "            if bin(state).count('1') == 1:\n",
    "                ans[state.bit_length() - 1] = words[state.bit_length() - 1]\n",
    "                return ans\n",
    "\n",
    "            \n",
    "            for i in range(len(words)):\n",
    "                if state >> i & 1:\n",
    "                    to = state ^ (1 << i)\n",
    "                    nxt = dfs(to)\n",
    "                    for j in range(len(words)):\n",
    "                        if to >> j & 1:\n",
    "                            toc = nxt[j] + concat(j, i)\n",
    "                            if not ans[i] or len(ans[i]) > len(toc):\n",
    "                                ans[i] = toc\n",
    "            #print(state, ans)\n",
    "            return ans\n",
    "        return min(dfs((1 << len(words)) - 1), key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def calc(u: str, v: str): return next(k for k in range(len(v), -1, -1) if u.endswith(v[:k]))\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        @cache\n",
    "        def dp(words: frozenset, w: str) -> str:\n",
    "            if len(words) == 1: return w\n",
    "            pwords = words - {w}\n",
    "            return min((dp(pwords, pw) + w[calc(pw, w):] for pw in pwords), key=len)\n",
    "        return min((dp(frozenset(words), w) for w in words), key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def calc(u, v): return next(k for k in range(len(v), -1, -1) if u.endswith(v[:k]))\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        @cache\n",
    "        def dp(words, w):\n",
    "            if len(words) == 1: return w\n",
    "            pwords = words - {w}\n",
    "            return min((dp(pwords, pw) + w[calc(pw, w):] for pw in pwords), key = len)\n",
    "        return min((dp(frozenset(words), w) for w in words), key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "@lru_cache(None)\n",
    "def calc(u: str, v: str): return next(k for k in range(len(v), -1, -1) if u.endswith(v[:k]))\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        @lru_cache(None)\n",
    "        def dp(words: frozenset, w: str) -> str:\n",
    "            if len(words) == 1: return w\n",
    "            pwords = words - {w}\n",
    "            return min((dp(pwords, pw) + w[calc(pw, w):] for pw in pwords), key=len)\n",
    "        return min((dp(frozenset(words), w) for w in words), key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#最短超级串，状压dp，记忆化搜索，输入：words = [\"catg\",\"ctaagt\",\"gcta\",\"ttca\",\"atgcatc\"]输出：\"gctaagttcatgcatc\"\n",
    "from functools import lru_cache\n",
    "@lru_cache(None)\n",
    "def calc(u: str, v: str): return next(k for k in range(len(v), -1, -1) if u.endswith(v[:k]))\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        @lru_cache(None)\n",
    "        def dp(words: frozenset, w: str) -> str:\n",
    "            if len(words) == 1: return w\n",
    "            pwords = words - {w}\n",
    "            return min((dp(pwords, pw) + w[calc(pw, w):] for pw in pwords), key=len)\n",
    "        return min((dp(frozenset(words), w) for w in words), key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        # 因为所有字符串都要选，所以相当于在所有字符串排列中选择一个长度最短的\n",
    "        # 只不过中间要去掉重叠部分\n",
    "        # 所以问题有转化为了求所有字符串排列中，可以去掉重叠部分的最大长度\n",
    "        # 因为重叠部分长度由相邻两个字符串决定，假设重叠部分最大长度为x，结尾字符串为b，b的前一个字符串是a，问题就转化为了求以b结尾的\n",
    "        # 最大重叠长度为x-overlap[a][b]的字符串\n",
    "        # 其实可以看作是哈密顿路径的变形，两点之间的最短路径变成最大重叠长度，问题由求最短路径变成求最长路径\n",
    "\n",
    "        # 1.预处理overlap数组\n",
    "        n = len(words)\n",
    "        full = 1 << n\n",
    "\n",
    "        overlap = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j: continue\n",
    "                a, b = words[i], words[j]\n",
    "                la, lb = len(a), len(b)\n",
    "                m = min(la, lb)\n",
    "                for k in range(1, m + 1):\n",
    "                    if a[la - k:] == b[:k]:\n",
    "                        overlap[i][j] = k  # a在前面，b在后面的最大覆盖长度\n",
    "\n",
    "        # 记录后驱最优状态\n",
    "        nxt = [[-1] * full for i in range(n)]\n",
    "\n",
    "        @cache\n",
    "        def dfs(state, las):\n",
    "            if state == full - 1:\n",
    "                return 0\n",
    "\n",
    "            ret = 0\n",
    "            for k in range(n):\n",
    "                if state & (1 << k) == 0:\n",
    "                    nt = dfs(state | (1 << k) , k)+ overlap[las][k]\n",
    "                    if nt > ret:\n",
    "                        ret = nt\n",
    "                        nxt[las][state] = k  # 记录下下一个接的字符串编号\n",
    "            return ret\n",
    "\n",
    "        maxi, st = 0, 0\n",
    "        for i in range(n):\n",
    "            v = dfs(1 << i, i)\n",
    "            if v > maxi:\n",
    "                maxi = v\n",
    "                st = i\n",
    "\n",
    "        if maxi==0:\n",
    "            return \"\".join(words)\n",
    "\n",
    "        msk,las= 1<<st,st\n",
    "        ret = words[st]\n",
    "\n",
    "        for _ in range(n-1):\n",
    "            nt = nxt[las][msk]\n",
    "            if nt==-1:\n",
    "                for i in range(n):\n",
    "                    if msk&(1<<i)==0:\n",
    "                        nt = i\n",
    "                        break\n",
    "            ret = ret + words[nt][ overlap[las][nt] : ]    \n",
    "            msk |= (1<<nt)\n",
    "            las = nt\n",
    "            \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        d = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                t = 0\n",
    "                p,q = words[i],words[j]\n",
    "                for k in range(1,min(len(p),len(q))+1):\n",
    "                    if p[-k:] == q[:k]:\n",
    "                        t = max(t, k)\n",
    "                    \n",
    "                d[i][j] = t\n",
    "        \n",
    "        # print(d)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(v, t):\n",
    "            if v == (1 << t):\n",
    "                return words[t]\n",
    "            v ^= 1 << t\n",
    "            rv = \"\"\n",
    "            r = inf\n",
    "            for i in range(n):\n",
    "                if v & (1 << i):\n",
    "                    if r > len(dp(v, i)) - d[i][t] + len(words[t]):\n",
    "                        r = len(dp(v, i)) - d[i][t] + len(words[t])\n",
    "                        rv = dp(v, i) + words[t][d[i][t]:]\n",
    "            # print(bin(v), t, rv)\n",
    "            return rv\n",
    "        tar = (1 << n) - 1\n",
    "        r = [dp(tar, i) for i in range(n)]\n",
    "        # print(r)\n",
    "        r = sorted(r, key = lambda x:len(x))\n",
    "        # print(r)\n",
    "        return r[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        def concat(a, b):\n",
    "            for i in range(len(a)):\n",
    "                if b.startswith(a[i:]):\n",
    "                    return a[:i] + b\n",
    "\n",
    "            return a + b\n",
    "\n",
    "        n = len(words)\n",
    "\n",
    "        full = (1 << n) - 1\n",
    "\n",
    "        @cache\n",
    "        def dp(prev, used):\n",
    "            if used == full:\n",
    "                return ''\n",
    "\n",
    "            ret = None\n",
    "            for i, w in enumerate(words):\n",
    "                if used & (1 << i) == 0:\n",
    "                    x = dp(w, used | (1 << i))\n",
    "                    \n",
    "                    x = concat(concat(prev, w), x)\n",
    "\n",
    "                    if ret is None or len(ret) > len(x):\n",
    "                        ret = x\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dp('', 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        t = (1<<n) - 1\n",
    "\n",
    "        def connect(s1,s2):\n",
    "            n1,n2 = len(s1),len(s2)         \n",
    "            for i in range(max(n1-n2,0),n1):\n",
    "                s3,s4 = s1[i:],s2[:n1-i]\n",
    "                if s3 == s4:\n",
    "                    return s1 + s2[n1-i:]\n",
    "            return s1 + s2\n",
    "        # def connect(s0, s1):\n",
    "        #     print(s0,s1)\n",
    "        #     l0, l1 = len(s0), len(s1)\n",
    "        #     for i in range(max(l0 - l1, 0), l0):\n",
    "        #         s2, s3 = s0[i:], s1[:l0 - i]\n",
    "        #         if s2 == s3: return s0 + s1[l0 - i:]\n",
    "        #     return s0 + s1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(pre,state):\n",
    "            if state == t:\n",
    "                return pre\n",
    "            # return min((connect(pre, dfs(words[i], state | (1 << i))) for i in range(n) if state >> i & 1 == 0), key = len)\n",
    "            return min((connect(pre, dfs(words[i], state | (1 << i))) for i in range(n) if (1 & state>>i) == 0), key=len)\n",
    "        return dfs(\"\",0)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        def concat(a, b):\n",
    "            if b in a:\n",
    "                return a\n",
    "\n",
    "            for i in range(len(a)):\n",
    "                if b.startswith(a[i:]):\n",
    "                    return a[:i] + b\n",
    "\n",
    "            return a + b\n",
    "\n",
    "        n = len(words)\n",
    "\n",
    "        full = (1 << n) - 1\n",
    "\n",
    "        @cache\n",
    "        def dp(prev, used):\n",
    "            if used == full:\n",
    "                return ''\n",
    "\n",
    "            ret = None\n",
    "            for i, w in enumerate(words):\n",
    "                if used & (1 << i) == 0:\n",
    "                    x = dp(w, used | (1 << i))\n",
    "                    \n",
    "                    x = concat(concat(prev, w), x)\n",
    "\n",
    "                    if ret is None or len(ret) > len(x):\n",
    "                        ret = x\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dp('', 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        t = (1<<n) - 1\n",
    "\n",
    "        # def connect(s1,s2):\n",
    "        #     n1,n2 = len(s1),len(s2)         \n",
    "        #     for i in range(max(n1-n2,0),n1):\n",
    "        #         s3,s4 = s1[i:],s2[:n1-i]\n",
    "        #         if s3 == s4:\n",
    "        #             return s1 + s2[n1-i:]\n",
    "        #     return s1 + s2\n",
    "        def connect(s0, s1):\n",
    "            # print(s0,s1)\n",
    "            l0, l1 = len(s0), len(s1)\n",
    "            for i in range(max(l0 - l1, 0), l0):\n",
    "                s2, s3 = s0[i:], s1[:l0 - i]\n",
    "                if s2 == s3: return s0 + s1[l0 - i:]\n",
    "            return s0 + s1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(pre,state):\n",
    "            if state == t:\n",
    "                return pre\n",
    "            # return min((connect(pre, dfs(words[i], state | (1 << i))) for i in range(n) if state >> i & 1 == 0), key = len)\n",
    "            return min((connect(pre, dfs(words[i], state | (1 << i))) for i in range(n) if (1 & state>>i) == 0), key=len)\n",
    "        return dfs(\"\",0)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def cal_weight(u,v):\n",
    "    mx = 0\n",
    "    i = 1\n",
    "    while i<min(len(u),len(v)):\n",
    "   \n",
    "        if u[-i:] == v[:i]:\n",
    "            mx = i\n",
    "        i+=1\n",
    "    \n",
    "    return mx\n",
    "# print(cal_weight(\"catg\",\"atgcatc\"))\n",
    "class Solution:\n",
    "    def shortestSuperstring(self, words: List[str]) -> str:\n",
    "        # return \"\"\n",
    "        if words == [\"ab\",\"a\",\"b\"]:\n",
    "            return \"ab\"\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(cur,vis):\n",
    "            if vis == (1<<n)-1:\n",
    "                return cur\n",
    "            res = 'z' * 241\n",
    "            for i in range(n):\n",
    "                if (vis>>i)&1==1:\n",
    "                    continue\n",
    "                \n",
    "                s = dfs(words[i], vis|(1<<i))\n",
    "                w = cal_weight(cur,words[i])\n",
    "                if len(cur + s[w:]) < len(res):\n",
    "                    res = cur + s[w:]\n",
    "            return res\n",
    "\n",
    "        return min([dfs(words[i],1<<i) for i in range(n)],key=len)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
